Search results for "Star-shaped polygon"
showing 2 items of 2 documents
Optimal Guard Placement Problem Under L-Visibility
2006
Two points a and b in the presence of polygonal obstacles are L-visible if the length of the shortest path avoiding obstacles is no more than L. For a given convex polygon Q, Gewali et al [4]. addressed the guard placement problem on the exterior boundary that will cover the maximum area exterior to the polygon under L-visibility. They proposed a linear time algorithm for some given value of L. When the length L is greater than half of the perimeter, they declared that problem as open. Here we address that open problem and present an algorithm whose time complexity is linear in number of vertices of the polygon.
A more efficient method for clustering sheet metal shapes
2007
The nesting of two-dimensional irregular shapes is a common problem which is frequently encountered by a number of industries where raw material has to be, as economically as possible, cut from a given stock sheet. A frequently recurring problem as far as cutting stock is concerned, is how to obtain the best nesting of some pieces of flat patterns which occupy minimalarea convex enclosure. The area of convex enclosure is related to the convex hull of the union of patterns which can be imagined as a large rubber band surrounding the set of all polygons. Our goal is to automatically obtain the smallest area convex shape containing all the patterns. As a matter of fact, Cheng and Rao have prop…